package chp01.YusufRing;

abstract class JosephItem {
    public JosephItem next;

    public JosephItem(JosephItem nextOne) {
        this.next = nextOne;
    }

    abstract int out();
}

class JosephCounter extends JosephItem {
    private int number;
    private int placeNow;

    public JosephCounter(int numberNow) {
        super(null);
        this.number = numberNow;
        this.placeNow = 0;
    }

    public int out() {
        //只做输出，并不判断产生的下一个人是不是已经退出环
        placeNow = placeNow % number + 1;
        return placeNow;
    }
}

class JosephFilter extends JosephItem {
    private int filtNum;

    public JosephFilter(JosephItem nextOne, int filtNumNow) {
        super(nextOne);
        filtNum = filtNumNow;
    }

    int out() {
        int temp = next.out();
        //会判断是否和自己的值相同，若相同，就说明当前报数的人已经退出环，
        // 就需要再次调用链表中下一个item的out()方法
        while (temp == filtNum) {
            temp = next.out();
        }
        return temp;
    }
}

class JosephSieve extends JosephItem {
    private int numberOfCir;
    private int m;

    public JosephSieve(int number, int mNum) {
        super(new JosephCounter(number));
        this.numberOfCir = number;
        this.m = mNum;
    }

    int out() {
        int x = 0;
        for (int i = 0; i < m; i++) {
            x = next.out();
        }
        next = new JosephFilter(next, x);
        return x;
    }
}

public class JosephCircleOOP_Ziwen {
    public static void main(String[] args) {
        // int n = 5, M = 3;
        // int n = 100, M = 5;
        int n = 1000, M = 7;

        long startTime = System.currentTimeMillis(); //获取开始时间
        JosephSieve sieve = new JosephSieve(n, M);
        // 每次筛选一个，筛选n次，最后一次筛选出的就是最后留下来的人
        for (int i = 0; i < n; i++) {
            int out = sieve.out();
            System.out.println("Filtered out number at time (" + i + ") is " + out);
            // if (i == n-1)
            //     System.out.println("The last number left is: " + out);
        }
        long endTime = System.currentTimeMillis(); //获取结束时间

        System.out.println("Total Running Time is: " + (endTime - startTime) + "ms"); //输出程序运行时间
    }
}
